package chapter1;
/**
 * "3N+1 Problem"
 * 
 * Consider the following algorithm to generate a sequence of numbers. Start
 * with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and
 * add 1. Repeat this process with the new value of n, terminating when n = 1.
 * For example, the following sequence of numbers will be generated for n = 22:
 * 
 * 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 It is conjectured (but not yet
 * proven) that this algorithm will terminate at n = 1 for every integer n.
 * Still, the conjecture holds for all integers up to at least 1, 000, 000.
 * 
 * For an input n, the cycle-length of n is the number of numbers generated up
 * to and including the 1. In the example above, the cycle length of 22 is 16.
 * Given any two numbers i and j, you are to determine the maximum cycle length
 * over all numbers between i and j, including both endpoints.
 * 
 * Input The input will consist of a series of pairs of integers i and j, one
 * pair of integers per line. All integers will be less than 1,000,000 and
 * greater than 0.
 * 
 * Output For each pair of input integers i and j, output i, j in the same order
 * in which they appeared in the input and then the maximum cycle length for
 * integers between and including i and j. These three numbers should be
 * separated by one space, with all three numbers on one line and with one line
 * of output for each line of input.
 * 
 * Sample Input
 * 
 * 1 10 100 200 201 210 900 1000
 * 
 * Sample Output
 * 
 * 1 10 20 100 200 125 201 210 89 900 1000 174
 * 
 * @author Kenny
 */
public class ThreeN_Plus_One_Problem 
{
	/*
	 * Algorithm: Approach problem in a linear fashion by evaluating each number
	 * between i and j. For each number, perform operations and count until we
	 * reach 1 (assuming that it does reach 1). Proceed to the next number and
	 * continue until it reaches 1 and determine if current count > old count.
	 * If yes, replace old count with current. After we finish computing j,
	 * increment 2 to current count as we need to include the i and j endpoints.
	 */
	public static void main (String [] args)
	{
		threeN_Sol2(10, 1);
	}
	
	public void threeN_Sol1(int i, int j)
	{
		int tempCount = 0;
		int currentCount = 0;
		
		for (int n = i; n <= j; n++)
		{
			int tempValue = n;
			
			while (tempValue != 1)
			{
				// Determine if tempValue is odd or even.
				if (tempValue % 2 == 0) // Even.
				{
					// n / 2.
					tempValue = tempValue / 2;
				} else { // Odd
					// 3 * n + 1.
					tempValue = (tempValue * 3) + 1;
				}
				tempCount++;
			}
			
			if (tempCount >= currentCount)
			{
				currentCount = tempCount;
			}
				tempCount = 0;
		}
		
		System.out.println(i + " " + j + " " + (currentCount + 2));	
	}
	
	public static void threeN_Sol2(int i, int j)
	{	
		if (i > j)
		{
			// Swap.
			int temp = i;
			i = j;
			j = temp;
		}
	
		long [] array = new long[j + 1];
		
		for (int n = i; n < array.length; n++)
		{
			long value = n;
			
			while (value != 1)
			{
				if (value % 2 == 0)
				{
					value = value / 2;
				} else {
					value = (value * 3) + 1;
				}
				
				array[n]++;
				
				if (value < array.length)
				{
					if (array[(int)value] != 0)
					{
						array[n] += array[(int)value];
						break;
					}
				}
			}
		}
		
		System.out.println(i + " " + j + " " + (search(array) + 1));
	}
	
	public static long search(long [] array)
	{
		long temp = 0;
		
		for (int i = 1; i < array.length; i++)
		{
			if (array[i] > temp)
			{
				temp = array[i];
			}
		}
		
		return temp;
	}
}
